{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Magical String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: magicalString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #神奇字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>神奇字符串 <code>s</code> 仅由 <code>'1'</code> 和 <code>'2'</code> 组成，并需要遵守下面的规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>神奇字符串 s 的神奇之处在于，串联字符串中 <code>'1'</code> 和 <code>'2'</code> 的连续出现次数可以生成该字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>s</code> 的前几个元素是 <code>s = \"1221121221221121122……\"</code> 。如果将 <code>s</code> 中连续的若干 <code>1</code> 和 <code>2</code> 进行分组，可以得到 <code>\"1 22 11 2 1 22 1 22 11 2 11 22 ......\"</code> 。每组中 <code>1</code> 或者 <code>2</code> 的出现次数分别是 <code>\"1 2 2 1 1 2 1 2 2 1 2 2 ......\"</code> 。上面的出现次数正是 <code>s</code> 自身。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，返回在神奇字符串 <code>s</code> 的前 <code>n</code> 个数字中 <code>1</code> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>神奇字符串 s 的前 6 个元素是 “<code>122112</code>”，它包含三个 1，因此返回 3 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [magical-string](https://leetcode.cn/problems/magical-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [magical-string](https://leetcode.cn/problems/magical-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = \"122\"\n",
    "        i = 2\n",
    "        while(len(s) < n and i < len(s)):\n",
    "            if(i%2 == 0):\n",
    "                s += \"1\" * int(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                s += \"2\" * int(s[i])\n",
    "                i += 1\n",
    "        return s[:n].count('1')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s=\"1221121221221121122\"\n",
    "        slow,fast=12,len(s)\n",
    "        while len(s)<n:\n",
    "            this=str(int(s[-1])%2+1)\n",
    "            s+=this*int(s[slow])\n",
    "            slow+=1\n",
    "        return Counter(s[:n])['1']\n",
    "# 1221121221221121122"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = \"122\"\n",
    "        i = 2\n",
    "        cnt = 1\n",
    "        j = 2\n",
    "        while j < n:\n",
    "            c = int(s[i])\n",
    "            if s[-1] == \"2\":\n",
    "                s += \"1\" * c\n",
    "                if j + c >= n:\n",
    "                    return cnt + n - j - 1\n",
    "                cnt += c\n",
    "            else:\n",
    "                s += \"2\" * c\n",
    "            j += c\n",
    "            i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = '122'\n",
    "        k = 1\n",
    "        for i in range(2, n):\n",
    "            cnt = int(s[i])\n",
    "            for j in range(cnt):\n",
    "                s += str(k)\n",
    "            k = 3 - k\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '1':\n",
    "                res += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = \"122\"\n",
    "        i = 2\n",
    "        # cnt = 1\n",
    "        j = 3\n",
    "        while j < n:\n",
    "            # c = int(s[i])\n",
    "            # if s[-1] == \"2\":\n",
    "            #     s += \"1\" * c\n",
    "            #     if j + c >= n:\n",
    "            #         return cnt + n - j - 1\n",
    "            #     cnt += c\n",
    "            # else:\n",
    "            #     s += \"2\" * c\n",
    "            # j += c\n",
    "            k='1' if s[-1]=='2' else '2'\n",
    "            c = int(s[i])\n",
    "            s += k*c\n",
    "            j += c\n",
    "            i += 1\n",
    "        # return cnt\n",
    "        return s[:n].count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        pre = \"122\"\n",
    "        jil = \"12\"\n",
    "        d = {}\n",
    "        if n <= len(pre):\n",
    "            for i in pre[:n]:\n",
    "                if i not in d:\n",
    "                    d[i] = 0\n",
    "                d[i]+=1\n",
    "            return d[\"1\"]\n",
    "        else:\n",
    "            for i in pre:\n",
    "                if i not in d:\n",
    "                    d[i] = 0\n",
    "                d[i]+=1\n",
    "            while len(pre) < n:\n",
    "                x = len(jil)\n",
    "                zifu = str(3-int(pre[-1]))\n",
    "                if pre[x] == \"1\":\n",
    "                    pre += zifu\n",
    "                    d[zifu] += 1\n",
    "                    jil += \"1\"\n",
    "                else:\n",
    "                    pre += zifu*2\n",
    "                    d[zifu] += 2 \n",
    "                    jil += \"2\"\n",
    "            if len(pre) > n and pre[-1] == \"1\": # 防止最后一次加两个一超限制\n",
    "                d[\"1\"] -= 1\n",
    "            return d[\"1\"]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return 1\n",
    "        if n == 4:\n",
    "            return 2\n",
    "        s1 = '122'\n",
    "        s2 = '12'\n",
    "        l1 = len(s1)-1\n",
    "        l2 = len(s2)-1\n",
    "        res = 1\n",
    "        while l1 < n:\n",
    "            l2 += 1\n",
    "            s2 += s1[l2]\n",
    "            if s1[-1] == '1':\n",
    "                s1 += int(s2[l2])*'2'\n",
    "            else:\n",
    "                if l1 + int(s2[l2]) >= n:\n",
    "                    res += (n-l1)\n",
    "                else:\n",
    "                    res += int(s2[l2])\n",
    "                s1 += int(s2[l2])*'1'\n",
    "            l1 = len(s1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        start = 1\n",
    "        lst = [1]\n",
    "        result = 1\n",
    "        front = 0\n",
    "        rear = 0\n",
    "        while(rear <= n-1):\n",
    "            if lst[front] == 1:\n",
    "                rear+=1\n",
    "                front+=1\n",
    "                if start == 1:\n",
    "                    start = 2\n",
    "                else:\n",
    "                    start = 1\n",
    "                    result += 1\n",
    "                lst.append(start)\n",
    "            else:\n",
    "                result += 1\n",
    "                lst.append(start)\n",
    "                rear+=2\n",
    "                front+=1\n",
    "                if start == 1:\n",
    "                    start = 2\n",
    "                else:\n",
    "                    start = 1\n",
    "                lst.append(start)\n",
    "        if rear == n:\n",
    "            result -= (2-lst[rear])\n",
    "        else:\n",
    "            result -= 2-lst[rear]\n",
    "            result -= 2 - lst[rear - 1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "\n",
    "        s = ['2']\n",
    "        for i in s:\n",
    "            if len(s) + 3 > n:\n",
    "                break\n",
    "            if i == '1':\n",
    "                if s[-1] == '1':\n",
    "                    s.append('2')\n",
    "                elif s[-1] == '2':\n",
    "                    s.append('1')\n",
    "            elif i == '2':\n",
    "                if s[-1] == '1':\n",
    "                    s.append('2')\n",
    "                    s.append('2')\n",
    "                elif s[-1] == '2':\n",
    "                    s.append('1')\n",
    "                    s.append('1')\n",
    "        count = 1\n",
    "        for x, num in enumerate(s):\n",
    "            if x == n - 2:\n",
    "                break\n",
    "            if num == '1':\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        lst = [1,2,2]\n",
    "        n1 = 1\n",
    "        n2 = 2\n",
    "        ns = 3\n",
    "        flag = 1\n",
    "        i = 2\n",
    "        while ns < n:\n",
    "            if flag == 1:\n",
    "                lst += lst[i] * [1]\n",
    "                n1 += lst[i]\n",
    "                ns += lst[i]\n",
    "                if ns > n: n1 -= 1\n",
    "                # print(\"flag==1:\",n1,n2,ns,lst)\n",
    "            elif flag == -1:\n",
    "                lst += lst[i] * [2]\n",
    "                n2 += lst[i]\n",
    "                ns += lst[i]\n",
    "                if ns > n: n2 -= 1\n",
    "                # print(\"flag==2:\",n1,n2,ns,lst)\n",
    "            flag *= -1\n",
    "            i += 1\n",
    "        return n1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return 1\n",
    "        p, chars = 2, [1, 2, 2]\n",
    "        while len(chars) < n:\n",
    "            chars.extend([3 - chars[-1]] * chars[p])\n",
    "            p += 1\n",
    "        while len(chars) > n:\n",
    "            chars.pop()\n",
    "        return 2 * n - sum(chars)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        if n <= 3:\n",
    "            return 1\n",
    "        strList = [0]*n \n",
    "        strList[:3] = [1,2,2]\n",
    "        res, i, j = 1, 2, 3\n",
    "        while j < n:\n",
    "            size = strList[i]\n",
    "            value = 3-strList[j-1]\n",
    "            while size > 0 and j < n:\n",
    "                strList[j] = value\n",
    "                if value == 1:\n",
    "                    res += 1\n",
    "                size -= 1\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        \n",
    "        res = 1\n",
    "        s = [0] * (n + 1)\n",
    "        s[:3] = [1, 2, 2]\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            num = s[j-1] ^ 3\n",
    "            if s[i] == 1:\n",
    "                s[j] = num\n",
    "                j += 1\n",
    "            else:\n",
    "                s[j] = s[j+1] = num\n",
    "                j += 2\n",
    "            if num == 1:\n",
    "                res += s[i]\n",
    "                if j > n:\n",
    "                    res -= 1\n",
    "            i += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        i, j, nums = 1, 3, [1, 2, 2]\n",
    "        while j < n:\n",
    "            i += 1\n",
    "            if i < n:\n",
    "                nums.extend([2 if i % 2 else 1]*nums[i])\n",
    "                j += nums[i]\n",
    "\n",
    "        return Counter(nums[:n])[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(s) < n:\n",
    "            pre = s[-1]\n",
    "            cur = 3 - pre\n",
    "            s += [cur] * s[i]\n",
    "            i += 1\n",
    "        return s[:n].count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(s) < n:\n",
    "            s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "            i += 1\n",
    "        return s[:n].count(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        res = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(res) < n:\n",
    "            # 保证当前数字在1和2切换\n",
    "            pre = res[-1]\n",
    "            cur = 3 - pre\n",
    "\n",
    "            # cur 表示这一组数字，s[i] 表示这一组数字出现的次数\n",
    "            res += [cur] * res[i]\n",
    "            i += 1\n",
    "        return res[:n].count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s=[1,2,2]\n",
    "        i=2\n",
    "        k=0\n",
    "        if n<=3:\n",
    "            return 1\n",
    "        while len(s)<n:\n",
    "            for jk in range(s[i]):\n",
    "                if k%2==0:\n",
    "                    s.append(1)\n",
    "                else:\n",
    "                    s.append(2)\n",
    "            i+=1\n",
    "            k+=1\n",
    "        return s[:n].count(1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(s) < n:\n",
    "            s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "            i += 1\n",
    "        return s[:n].count(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1,2,2]\n",
    "\n",
    "        idx = 2\n",
    "\n",
    "        while len(s)<n:\n",
    "            s+=s[idx]*[s[-1]^3]\n",
    "            idx+=1\n",
    "        \n",
    "\n",
    "        return s[:n].count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def magicalString(self, n: int) -> int:\r\n",
    "        segments=[1]\r\n",
    "        counter_idx=0\r\n",
    "        # total=1\r\n",
    "        while len(segments)<n:\r\n",
    "            next_char=1 if segments[-1]==2 else 2\r\n",
    "            segments.append(next_char)\r\n",
    "            counter_idx+=1\r\n",
    "            # total\r\n",
    "            if segments[counter_idx]==2:\r\n",
    "                segments.append(next_char)\r\n",
    "        \r\n",
    "        cnt=0\r\n",
    "        for i in segments[:n]:\r\n",
    "            if i==1:\r\n",
    "                cnt+=1\r\n",
    "        return cnt\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        p1 = ['1', '2']\n",
    "        p2 = ['1',]\n",
    "        s = 1\n",
    "\n",
    "        while len(p1) < n:\n",
    "            for i in range(s, len(p1)):\n",
    "                c = '1' if p2[-1] == '2' else '2'\n",
    "                p2.extend([c]*int(p1[i]))\n",
    "            s = len(p1)\n",
    "            p1 += p2[len(p1):]\n",
    "        p1 = p1[:n]\n",
    "        return p1.count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "      s = [1,2,2]\n",
    "      i = 2\n",
    "      ans = 1\n",
    "      if n < 4:\n",
    "        return ans\n",
    "      while i < n:\n",
    "        if s[i] == 1:\n",
    "          ans += 1\n",
    "          if s[-1] == 1:\n",
    "            s.append(2)\n",
    "          else:\n",
    "            s.append(1)\n",
    "        else:\n",
    "          if s[-1] == 1:\n",
    "            s.append(2)\n",
    "            s.append(2)\n",
    "          else:\n",
    "            s.append(1)\n",
    "            s.append(1)\n",
    "        \n",
    "        i += 1\n",
    "      print(s)\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.raw_list = [1, 2, 2]\n",
    "        self.freq_list = [1, 2]\n",
    "        self.raw_index = 1\n",
    "\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        n_fetch = self.fetch(n)\n",
    "        return sum([1 for n_raw in n_fetch if n_raw == 1])\n",
    "\n",
    "    def fetch(self, n: int) -> List[int]:\n",
    "        current_raw_len = len(self.raw_list)\n",
    "        # expand raw list\n",
    "        while n > current_raw_len > self.raw_index + 1:\n",
    "            added_freq = self.raw_list[self.raw_index + 1]\n",
    "            self.freq_list.append(added_freq)\n",
    "            added_raw = [1] if self.raw_list[current_raw_len - 1] == 2 else [2]\n",
    "            self.raw_list += added_raw * added_freq\n",
    "            current_raw_len += added_freq\n",
    "            self.raw_index += 1\n",
    "\n",
    "        return self.raw_list[:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "upper = [1, 22, 11,2]\n",
    "lower = [1, 2,  2, 1, 1,2]\n",
    "for lower_idnex in range(4,66666):\n",
    "    if lower[lower_idnex] == 1:\n",
    "        # 加1个\n",
    "        if upper[lower_idnex-1] %10 == 2:\n",
    "            # 末尾加1\n",
    "            upper.append(1)\n",
    "            numbers = 1\n",
    "        else:\n",
    "            upper.append(2)\n",
    "            numbers = 2\n",
    "    else:\n",
    "        # 加2个\n",
    "        if upper[lower_idnex-1] %10 == 2:\n",
    "            # 末尾加1\n",
    "            upper.append(11)\n",
    "            numbers = 11\n",
    "        else:\n",
    "            upper.append(22)\n",
    "            numbers = 22\n",
    "    while numbers!=0:\n",
    "        lower.append(numbers%10)\n",
    "        numbers = numbers//10\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return lower[:n].count(1)\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s0 = list('122')\n",
    "        s_num = [1,2]\n",
    "        temp = {'1':['2'],'2':['1']}\n",
    "        i = 2\n",
    "        while len(s0) < n:\n",
    "            s_num.append(int(s0[i]))\n",
    "            s0.extend(temp[s0[-1]]*s_num[-1])\n",
    "            i += 1\n",
    "        s0 = s0[:n]\n",
    "        return s0.count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        ss = '01' # 首位多加一个 0 作为哨兵\n",
    "        i, j, cnt = 1, 1, 0\n",
    "        f = [0] * (n + 10)\n",
    "        while i <= n:\n",
    "            last, t = ss[i], ss[j]\n",
    "            if last == '1':\n",
    "                if t == '1':\n",
    "                    # 当原串当前字符是 1，而计数串当前字符为 1 \n",
    "                    # 往后构造形成的原串只能是 12，原串指针后移一位\n",
    "                    ss += '2'\n",
    "                    f[i], cnt, i = cnt + 1, cnt + 1, i + 1\n",
    "                else:\n",
    "                    # 当原串当前字符是 1，而计数串当前字符为 2\n",
    "                    # 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位\n",
    "                    ss += '12'\n",
    "                    f[i], f[i + 1], cnt, i = cnt + 1, cnt + 2, cnt + 2, i + 2\n",
    "            else:\n",
    "                if t == '1':\n",
    "                    # 当原串当前字符是 2，而计数串当前字符为 1 \n",
    "                    # 往后构造形成的原串只能是 21，原串指针后移一位\n",
    "                    ss += '1'\n",
    "                    f[i], i = cnt, i + 1\n",
    "                else:\n",
    "                    # 当原串当前字符是 2，而计数串当前字符为 2\n",
    "                    # 往后构造形成的原串只能是 221，原串指针后移两位\n",
    "                    ss += '21'\n",
    "                    f[i], f[i + 1], i = cnt, cnt, i + 2\n",
    "            j += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        ss = '01' # 首位多加一个 0 作为哨兵\n",
    "        i, j, cnt = 1, 1, 0\n",
    "        f = [0] * (n + 10)\n",
    "        while i <= n:\n",
    "            last, t = ss[i], ss[j]\n",
    "            if last == '1':\n",
    "                if t == '1':\n",
    "                    # 当原串当前字符是 1，而计数串当前字符为 1 \n",
    "                    # 往后构造形成的原串只能是 12，原串指针后移一位\n",
    "                    ss += '2'\n",
    "                    f[i], cnt, i = cnt + 1, cnt + 1, i + 1\n",
    "                else:\n",
    "                    # 当原串当前字符是 1，而计数串当前字符为 2\n",
    "                    # 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位\n",
    "                    ss += '12'\n",
    "                    f[i], f[i + 1], cnt, i = cnt + 1, cnt + 2, cnt + 2, i + 2\n",
    "            else:\n",
    "                if t == '1':\n",
    "                    # 当原串当前字符是 2，而计数串当前字符为 1 \n",
    "                    # 往后构造形成的原串只能是 21，原串指针后移一位\n",
    "                    ss += '1'\n",
    "                    f[i], i = cnt, i + 1\n",
    "                else:\n",
    "                    # 当原串当前字符是 2，而计数串当前字符为 2\n",
    "                    # 往后构造形成的原串只能是 221，原串指针后移两位\n",
    "                    ss += '21'\n",
    "                    f[i], f[i + 1], i = cnt, cnt, i + 2\n",
    "            j += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n <= 3: return 1\n",
    "        s = [1, 2, 2]\n",
    "        p = 2 # 下一个 group 的长度为 s[p]\n",
    "        while len(s) <= n:\n",
    "            s += [3 - s[-1]] * s[p]\n",
    "            p += 1\n",
    "        return sum([2-x for x in s[:n]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n <= 3: return 1\n",
    "        chrs = deque([\"1\", \"22\"])\n",
    "        cnts = deque([2])\n",
    "        i = 3\n",
    "        while i < n:\n",
    "            cnt = cnts.popleft()\n",
    "            if i + cnt > n:\n",
    "                cnt -= 1\n",
    "            i += cnt\n",
    "            if len(chrs) % 2 == 0:\n",
    "                chrs.append('1' * cnt)\n",
    "            else:\n",
    "                chrs.append('2' * cnt)\n",
    "            \n",
    "            if len(chrs[-1]) == 2:\n",
    "                cnts.append(int(chrs[-1]) // 10)\n",
    "                cnts.append(int(chrs[-1]) % 10)\n",
    "            else:\n",
    "                cnts.append(int(chrs[-1]))\n",
    "\n",
    "        return Counter(''.join(chrs))['1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        # 构造\n",
    "        strs = [1, 2, 2]\n",
    "        while len(strs) < n:\n",
    "            cnts, strs, cur = strs, [], 1\n",
    "            for cnt in cnts:\n",
    "                if cur == 1:\n",
    "                    strs += [1] * cnt\n",
    "                    cur = 2\n",
    "                else:\n",
    "                    strs += [2] * cnt\n",
    "                    cur = 1\n",
    "        return strs[:n].count(1)\n",
    "\n",
    "        # 求前 n 项和\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        # 构造\n",
    "        strs = [1, 2, 2, 1, 1]\n",
    "        while len(strs) < n:\n",
    "            cnts, strs, cur = strs, [], 1\n",
    "            for cnt in cnts:\n",
    "                if cur == 1:\n",
    "                    strs += [1] * cnt\n",
    "                    cur = 2\n",
    "                else:\n",
    "                    strs += [2] * cnt\n",
    "                    cur = 1\n",
    "        return strs[:n].count(1)\n",
    "\n",
    "        # 求前 n 项和\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr,end,p=[1,2,2],2,1\n",
    "while len(arr)<100005:\n",
    "    p+=1\n",
    "    a=arr[p]\n",
    "    end=3-end\n",
    "    for i in range(a):\n",
    "        arr.append(end)\n",
    "for i in range(1,100005):\n",
    "    arr[i]=arr[i-1]+2-arr[i]\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return arr[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        ss = '01'\n",
    "        i, j, cnt = 1, 1, 0\n",
    "        f = [0] * (n + 2);\n",
    "        while i <= n:\n",
    "            a, b = ss[i], ss[j]\n",
    "            if a == '1':\n",
    "                if b == '1':\n",
    "                    ss += '2'\n",
    "                    cnt += 1\n",
    "                    f[i] = cnt\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ss += '12'\n",
    "                    f[i], f[i + 1], cnt, i = cnt+1, cnt+2, cnt+2, i+2\n",
    "            else:\n",
    "                if b == '1':\n",
    "                    ss += '1'\n",
    "                    f[i] = cnt\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ss += '21'\n",
    "                    f[i], f[i + 1] = cnt, cnt\n",
    "                    i += 2\n",
    "            j += 1\n",
    "        return f[n]       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        # 构造\n",
    "        strs = [1, 2, 2, 1]\n",
    "        while len(strs) < n:\n",
    "            cnts, strs, cur = strs, [], 1\n",
    "            for cnt in cnts:\n",
    "                strs += [cur] * cnt\n",
    "                cur = 3 - cur\n",
    "                # if cur == 1:\n",
    "                #     strs += [1] * cnt\n",
    "                #     cur = 2\n",
    "                # else:\n",
    "                #     strs += [2] * cnt\n",
    "                #     cur = 1\n",
    "        return strs[:n].count(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "seq = [0, 1, 1, 2]\r\n",
    "cached_index = 3\r\n",
    "el = 1\r\n",
    "\r\n",
    "def gen_magic(n: int):\r\n",
    "    global cached_index, seq, el\r\n",
    "    while cached_index <= n:\r\n",
    "        repeat = seq[cached_index]\r\n",
    "        seq[cached_index] = seq[cached_index-1] + repeat%2\r\n",
    "        seq.extend([el] * repeat)\r\n",
    "        el = el%2+1\r\n",
    "        cached_index += 1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def magicalString(self, n: int) -> int:\r\n",
    "        if cached_index <= n:\r\n",
    "            gen_magic(n)\r\n",
    "        return seq[n]\r\n",
    "\r\n",
    "# s = [1, 2, 2]\r\n",
    "# i = 2\r\n",
    "# one = True\r\n",
    "# while len(s) <= 100000:\r\n",
    "#     s += [1 if one else 2] * s[i]\r\n",
    "#     one = not one\r\n",
    "#     i += 1\r\n",
    "# cnt = [0] * (len(s) + 1)\r\n",
    "# for i in range(len(s)):\r\n",
    "#     cnt[i + 1] = cnt[i] + (s[i] == 1)\r\n",
    "\r\n",
    "\r\n",
    "# class Solution:\r\n",
    "#     def magicalString(self, n: int) -> int:\r\n",
    "#         return cnt[n]\r\n",
    "\r\n",
    "if __name__ == '__main__':\r\n",
    "    pass\r\n",
    "    # solution = Solution()\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(19))\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(100000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "seq = [0, 1, 1, 2]\r\n",
    "cached_index = 3\r\n",
    "el = 1\r\n",
    "\r\n",
    "def gen_magic(n: int):\r\n",
    "    global cached_index, seq, el\r\n",
    "    while cached_index <= n:\r\n",
    "        repeat = seq[cached_index]\r\n",
    "        seq += [el] * repeat\r\n",
    "        seq[cached_index] = seq[cached_index-1] + repeat%2\r\n",
    "        el = el%2+1\r\n",
    "        cached_index += 1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "\r\n",
    "    def magicalString(self, n: int) -> int:\r\n",
    "        if cached_index <= n:\r\n",
    "            gen_magic(n)\r\n",
    "        return seq[n]\r\n",
    "\r\n",
    "# s = [1, 2, 2]\r\n",
    "# i = 2\r\n",
    "# one = True\r\n",
    "# while len(s) <= 100000:\r\n",
    "#     s += [1 if one else 2] * s[i]\r\n",
    "#     one = not one\r\n",
    "#     i += 1\r\n",
    "# cnt = [0] * (len(s) + 1)\r\n",
    "# for i in range(len(s)):\r\n",
    "#     cnt[i + 1] = cnt[i] + (s[i] == 1)\r\n",
    "\r\n",
    "\r\n",
    "# class Solution:\r\n",
    "#     def magicalString(self, n: int) -> int:\r\n",
    "#         return cnt[n]\r\n",
    "\r\n",
    "if __name__ == '__main__':\r\n",
    "    pass\r\n",
    "    # solution = Solution()\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(19))\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(100000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res,cur, end = [1, 2, 2],1, 2\n",
    "while cur < 100000:\n",
    "    cur += 1\n",
    "    end = 3 - end\n",
    "    for i in range(res[cur]):\n",
    "        res.append(end)\n",
    "for i in range(1,100001):\n",
    "    res[i] = res[i-1] + 2 - res[i]\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return res[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        ss = '01'\n",
    "        i,j,cnt = 1,1,0\n",
    "        f = [0] * (n+2)\n",
    "        while i<= n:\n",
    "            last,t = ss[i],ss[j]\n",
    "            if last == '1' :\n",
    "                if t == '1' :\n",
    "                    ss += '2'\n",
    "                    f[i],cnt,i = cnt+1,cnt+1,i+1\n",
    "                else :\n",
    "                    ss += '12'\n",
    "                    f[i],f[i+1],cnt,i = cnt+1,cnt+2,cnt+2,i+2\n",
    "            else :\n",
    "                if t == '1':\n",
    "                    ss += '1'\n",
    "                    f[i],i = cnt,i+1\n",
    "                else :\n",
    "                    ss += '21'\n",
    "                    f[i],f[i+1],i = cnt,cnt,i+2 \n",
    "            j += 1\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 5\n",
    "dp = [1] * n\n",
    "s = [0] * n\n",
    "s[0] = 1\n",
    "i = 2\n",
    "j = 3\n",
    "while j < n:\n",
    "    a = 0 if s[j-1] else 1\n",
    "    if s[i] == 1:\n",
    "        s[j] = a\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    else:\n",
    "        s[j] = a\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "        s[j] = a\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    i += 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 5\n",
    "dp = [1] * n\n",
    "s = [1,0,0]\n",
    "i = 2\n",
    "j = 3\n",
    "while j < n:\n",
    "    a = 0 if s[-1] else 1\n",
    "    if s[i] == 1:\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    else:\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    i += 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "one = True\n",
    "while len(s) <= 100000:\n",
    "    s += [1 if one else 2] * s[i]\n",
    "    one = not one\n",
    "    i += 1\n",
    "cnt = [0] * (len(s) + 1)\n",
    "for i in range(len(s)):\n",
    "    cnt[i + 1] = cnt[i] + (s[i] == 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return cnt[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 5\n",
    "dp = [1] * n\n",
    "s = [1,0,0]\n",
    "i = 2\n",
    "j = 3\n",
    "while j < n:\n",
    "    a = 0 if s[-1] else 1\n",
    "    if s[i] == 1:\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    else:\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "        s.append(a)\n",
    "        dp[j] = dp[j - 1] + a\n",
    "        j += 1\n",
    "    i += 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# seq = [0, 1, 1, 2]\r\n",
    "# cached_index = 3\r\n",
    "# el = 1\r\n",
    "\r\n",
    "# def gen_magic(n: int):\r\n",
    "#     global cached_index, seq, el\r\n",
    "#     while cached_index <= n:\r\n",
    "#         repeat = seq[cached_index]\r\n",
    "#         seq += [el] * repeat\r\n",
    "#         seq[cached_index] = seq[cached_index-1] + repeat%2\r\n",
    "#         el = el%2+1\r\n",
    "#         cached_index += 1\r\n",
    "\r\n",
    "# class Solution:\r\n",
    "\r\n",
    "#     def magicalString(self, n: int) -> int:\r\n",
    "#         if cached_index <= n:\r\n",
    "#             gen_magic(n)\r\n",
    "#         return seq[n]\r\n",
    "\r\n",
    "s = [1, 2, 2]\r\n",
    "i = 2\r\n",
    "one = True\r\n",
    "while len(s) <= 100000:\r\n",
    "    s += [1 if one else 2] * s[i]\r\n",
    "    one = not one\r\n",
    "    i += 1\r\n",
    "cnt = [0] * (len(s) + 1)\r\n",
    "for i in range(len(s)):\r\n",
    "    cnt[i + 1] = cnt[i] + (s[i] == 1)\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def magicalString(self, n: int) -> int:\r\n",
    "        return cnt[n]\r\n",
    "\r\n",
    "if __name__ == '__main__':\r\n",
    "    pass\r\n",
    "    # solution = Solution()\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(19))\r\n",
    "    # print(solution.magicalString(7))\r\n",
    "    # print(solution.magicalString(100000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        upper = [1, 22, 11,2]\n",
    "        lower = [1, 2,  2, 1, 1,2]\n",
    "        lower_idnex  = 4\n",
    "        ans = 0\n",
    "        if n<=6:\n",
    "            for i in range(n):\n",
    "                if lower[i] == 1: ans+=1\n",
    "            return ans\n",
    "        else:\n",
    "            # 需要生成\n",
    "            ans = 2\n",
    "            while lower_idnex<n:\n",
    "                numbers = None\n",
    "                if lower[lower_idnex] == 1:\n",
    "                    # 加个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(1)\n",
    "                        numbers = 1\n",
    "                    else:\n",
    "                        upper.append(2)\n",
    "                        numbers = 2\n",
    "                else:\n",
    "                    # 加2个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(11)\n",
    "                        numbers = 11\n",
    "                    else:\n",
    "                        upper.append(22)\n",
    "                        numbers = 22\n",
    "                \n",
    "                while numbers!=0:\n",
    "                    lower.append(numbers%10)\n",
    "                    numbers = numbers//10\n",
    "                if lower[lower_idnex] ==1 :ans+=1\n",
    "\n",
    "                lower_idnex+=1\n",
    "            return ans\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        upper = [1, 22, 11,2      ]\n",
    "        lower = [1, 2,  2, 1, 1,2]\n",
    "        lower_idnex  = 4\n",
    "        ans = 0\n",
    "        if n<=6:\n",
    "            for i in range(n):\n",
    "                if lower[i] == 1: ans+=1\n",
    "            return ans\n",
    "        else:\n",
    "            # 需要生成\n",
    "            ans = 2\n",
    "            while lower_idnex<n:\n",
    "                numbers = None\n",
    "                if lower[lower_idnex] == 1:\n",
    "                    # 加个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(1)\n",
    "                        numbers = 1\n",
    "                    else:\n",
    "                        upper.append(2)\n",
    "                        numbers = 2\n",
    "                else:\n",
    "                    # 加2个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(11)\n",
    "                        numbers = 11\n",
    "                    else:\n",
    "                        upper.append(22)\n",
    "                        numbers = 22\n",
    "                \n",
    "                while numbers!=0:\n",
    "                    lower.append(numbers%10)\n",
    "                    numbers = numbers//10\n",
    "                if lower[lower_idnex] ==1 :ans+=1\n",
    "\n",
    "                lower_idnex+=1\n",
    "            return ans\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        upper = [1, 22, 11,2      ]\n",
    "        lower = [1, 2,  2, 1, 1,2]\n",
    "        lower_idnex  = 4\n",
    "        ans = 0\n",
    "        if n<=6:\n",
    "            for i in range(n):\n",
    "                if lower[i] == 1: ans+=1\n",
    "            return ans\n",
    "        else:\n",
    "            # 需要生成\n",
    "            ans = 2\n",
    "            while lower_idnex<n:\n",
    "                numbers = None\n",
    "                if lower[lower_idnex] == 1:\n",
    "                    # 加个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(1)\n",
    "                        numbers = 1\n",
    "                    else:\n",
    "                        upper.append(2)\n",
    "                        numbers = 2\n",
    "                else:\n",
    "                    # 加2个\n",
    "                    if upper[lower_idnex-1] %10 == 2:\n",
    "                        # 末尾加1\n",
    "                        upper.append(11)\n",
    "                        numbers = 11\n",
    "                    else:\n",
    "                        upper.append(22)\n",
    "                        numbers = 22\n",
    "                \n",
    "                while numbers!=0:\n",
    "                    lower.append(numbers%10)\n",
    "                    numbers = numbers//10\n",
    "                if lower[lower_idnex] ==1 :ans+=1\n",
    "\n",
    "                lower_idnex+=1\n",
    "            return ans\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX = 10 ** 5 + 2\n",
    "\n",
    "ans = [1, 2, 2]\n",
    "\n",
    "i = 2\n",
    "for _ in range(2, MAX):\n",
    "    ans += [ans[-1] ^ 3] * ans[i]\n",
    "    i += 1\n",
    "s = [0] * MAX\n",
    "\n",
    "for i in range(1, MAX):\n",
    "    s[i] = s[i - 1] + 2 - ans[i - 1]\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return s[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "while len(s) < 10 ** 5:\n",
    "    s += [s[-1] ^ 3] * s[i]\n",
    "    i += 1\n",
    "\n",
    "acc = list(accumulate([2 - c for c in s], initial=0))\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return acc[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        books = [1, 2, 2]\n",
    "        count = [1] * (10 ** 5 + 10)\n",
    "        n = 10 ** 5\n",
    "        for i in range(2, n):\n",
    "            c = books[i]\n",
    "            if books[-1] == 1:\n",
    "                books.extend([2] * c)\n",
    "            else:\n",
    "                books.extend([1] * c)\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            c += books[i] == 1\n",
    "            count[i] = c\n",
    "        self.count = count\n",
    "\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return self.count[n - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def magicalString(self, n: int) -> int:\n",
    "#         s = [1, 2, 2]\n",
    "#         i = 2\n",
    "#         while len(s) < n:\n",
    "#             s += [s[-1] ^ 3] * s[i] # 1 ^ 3 = 2, 2 ^ 3 = 1, 这样就能在1和2之间转换\n",
    "#             i += 1\n",
    "#         return s[:n].count(1)\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "while len(s) < 100000:\n",
    "    s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "    i += 1\n",
    "acc = list(accumulate((2 - c for c in s), initial=0))  # 2-1=1，2-2=0，这样就只统计了 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return acc[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "while len(s) < 100000:\n",
    "    s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "    i += 1\n",
    "acc = list(accumulate((2 - c for c in s), initial=0))  # 2-1=1，2-2=0，这样就只统计了 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return acc[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 由于1 2 是交替出现，所以最新的元素是1 or 2是由s最后一个元素决定\r\n",
    "# 元素的个数则是s[i]决定\r\n",
    "# 关键点利用异或运算 ^, 2 ^ 3 = 1; 1 ^ 3 = 2\r\n",
    "# class Solution:\r\n",
    "#     def magicalString(self, n: int) -> int:\r\n",
    "#         s = [1, 2, 2]\r\n",
    "#         i = 2\r\n",
    "#         while len(s) < n:   \r\n",
    "#             s += [s[-1] ^ 3] * s[i] \r\n",
    "#             i += 1 \r\n",
    "#         return s[:n].count(1)   # 最后一个可能添加 1 or 2个新元素，所以 s[:n]\r\n",
    "\r\n",
    "\r\n",
    "s = [1, 2, 2]\r\n",
    "i = 2\r\n",
    "while len(s) < 100000:\r\n",
    "    s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\r\n",
    "    i += 1\r\n",
    "acc = list(accumulate((2 - c for c in s), initial=0))  # 2-1=1，2-2=0，这样就只统计了 1\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def magicalString(self, n: int) -> int:\r\n",
    "        return acc[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [1, 2, 2]\n",
    "ans = [1, 1, 1]\n",
    "idx = 2\n",
    "while len(ans) < 10 ** 5:\n",
    "    s.extend([s[-1] ^ 3] * s[idx])\n",
    "    idx += 1\n",
    "    while len(ans) < len(s):\n",
    "        ans.append(ans[-1] + (s[-1] & 1))\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return ans[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ans_dict={}\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s=\"122\"\n",
    "        str_ptr,group_ptr,ans=3,2,1\n",
    "        if n<=3:\n",
    "            return ans\n",
    "        if n in ans_dict:\n",
    "            return ans_dict[n]\n",
    "\n",
    "        while str_ptr<n:\n",
    "            if s[group_ptr]=='2':\n",
    "                if s[-1]==\"1\":\n",
    "                    s+=\"22\"\n",
    "                else:\n",
    "                    s+=\"11\"\n",
    "                    ans+=2\n",
    "                str_ptr+=2\n",
    "                group_ptr+=1\n",
    "            else:\n",
    "                if s[-1]==\"1\":\n",
    "                    s+=\"2\"\n",
    "                else:\n",
    "                    ans+=1\n",
    "                    s+=\"1\"\n",
    "                str_ptr+=1\n",
    "                group_ptr+=1\n",
    "            ans_dict[str_ptr]=ans\n",
    "        if str_ptr>n and s[-1]==\"1\":\n",
    "            ans-=1\n",
    "        ans_dict[n]=ans\n",
    "        return ans\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = ['' for _ in range(n)]\n",
    "        s[:3] = '122'\n",
    "        i, j = 2, 3\n",
    "        res = 1\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            aim_c = str(3 - int(s[j - 1]))\n",
    "            while size > 0 and j < n:\n",
    "                s[j] = aim_c\n",
    "                size -= 1\n",
    "                j += 1\n",
    "                if aim_c == '1':\n",
    "                    res += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        d = {'1': '2', '2': '1'}\n",
    "        s1 = ['1','22','11','2','1','22','1','22','11','2','11','22']\n",
    "        s2 = ['1','2', '2', '1','1','2', '1','2', '2', '1', '2', '2','1','1','2','1','1','2','2']\n",
    "        while len(s2) < n:\n",
    "            n1, n2 = len(s1), len(s2)\n",
    "            for i in range(n1, n2):\n",
    "                k = int(s2[i])\n",
    "                p = d.get(s1[-1][-1]) * k \n",
    "                s1.append(p)\n",
    "                s2.extend(list(p))\n",
    "        # print(\"\".join(s1))\n",
    "        return s2[:n].count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [''] * n\n",
    "        s[:3] = '122'\n",
    "        i, j = 2, 3\n",
    "        # 对于一次构造需要知道两个要素：值和长度\n",
    "        # 由于每一次构造需要和前一次相区别，故值必然发生变动\n",
    "        # 而长度将取自于每轮构造进 1 位的 i 所指向数字\n",
    "        # '122' 已经实现了对 '12' 的构造，故 i 从 2 起始\n",
    "        while j < n:\n",
    "            val = 3 - int(s[j - 1])\n",
    "            size = int(s[i])\n",
    "            s[j:j + size] = [str(val)] * 2\n",
    "            j += size\n",
    "            i += 1\n",
    "        return s[:n].count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "while len(s) < 100000:\n",
    "    s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "    i += 1\n",
    "acc = list(accumulate((2 - c for c in s), initial=0))  # 2-1=1，2-2=0，这样就只统计了 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return acc[n]\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(s) < n:\n",
    "            s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "            i += 1\n",
    "        return s[:n].count(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s='122'\n",
    "        cur=2\n",
    "        while len(s)<n:\n",
    "            if s[-1]=='1':\n",
    "                s+=int(s[cur])*'2'\n",
    "            else:\n",
    "                s+=int(s[cur])*'1'\n",
    "            cur+=1\n",
    "        return s[:n].count('1')\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "s = [1, 2, 2]\n",
    "i = 2\n",
    "while len(s) < 100000:\n",
    "    s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "    i += 1\n",
    "acc = list(accumulate((2 - c for c in s), initial=0))  # 2-1=1，2-2=0，这样就只统计了 1\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        return acc[n]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = [1, 2, 2]\n",
    "        i = 2\n",
    "        while len(s) < n:\n",
    "            s += [s[-1] ^ 3] * s[i]  # 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换\n",
    "            i += 1\n",
    "        return s[:n].count(1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s1 = ['1','2','2']\n",
    "        s2 = []\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        cur = '1'\n",
    "\n",
    "        while cnt < n:\n",
    "            if s1[i] == '1':\n",
    "                s2.append(cur)\n",
    "                cur = str(3 - int(cur))\n",
    "                i +=1\n",
    "                cnt +=1\n",
    "            else:\n",
    "                s2.append(cur)\n",
    "                s2.append(cur)\n",
    "                cur = str(3 - int(cur))\n",
    "                i += 1\n",
    "                cnt +=2\n",
    "            s1 += s2[len(s1):]\n",
    "        ans = 0\n",
    "        for i  in range(n):\n",
    "            if s2[i] == '1':\n",
    "                ans +=1\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [\"\"] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "#         str的构造：\n",
    "# index = 0，str = “”，尾部添加一个'1'，str更新为“1”\n",
    "# index = 1，str = “1”，尾部添加str[index] - '0' = 2个 ‘2’，str 更新为 “122”，\n",
    "# index = 2，str = “122”，尾部添加str[index] - '0' = 2个 ‘1’，str 更新为 “122 11”，\n",
    "# index = 3，str = “12211”，尾部添加str[index] - '0' = 1个 ‘2’，str更新为“12211 2”\n",
    "# index = 4，str = “122112”，尾部添加str[index] - '0' = 1个 ‘1’，str更新 “122112 1”，\n",
    "# index = 5，str = “1221121”，尾部添加str[index] - '0' = 2个 ‘2’，str更新为“1221121 22”\n",
    "# index = 6，str = “122112122”，尾部添加str[index] - '0' = 1个‘1’，str 更新 “122112122 1”，\n",
    "# index = 7，str = “1221121221”，尾部添加str[index] - '0' = 2个‘2’，str更新为“1221121221 22”\n",
    "# ...\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        ## i是索引，用于计算添加的个数s[i]\n",
    "        ## j是添加的位置\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            ## size就是添加的个数\n",
    "            num = 3 - int(s[j - 1])\n",
    "            ## 这次添加的数字，1或者2\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res\n",
    "        '''\n",
    "        if n <= 3:\n",
    "            return 1\n",
    "        s = \"122\"\n",
    "        flag , length , index = 1 , 3 , 2\n",
    "        while length < n:\n",
    "            if s[index] == '2':\n",
    "                length += 2\n",
    "                if flag == 1:\n",
    "                    s += '11'\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    s += '22'\n",
    "                    flag = 1\n",
    "            elif s[index] == '1':\n",
    "                length += 1\n",
    "                if flag == 1:\n",
    "                    s += '1'\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    s += '2'\n",
    "                    flag = 1\n",
    "            index += 1\n",
    "        return s[:n].count('1')\n",
    "        '''\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [\"\"] * n\n",
    "        s[:3] = \"122\"\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = '122'\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = ['1','2','2']\n",
    "        a, b = 2, 2\n",
    "        while a <= n:\n",
    "            temp = 1 if ord(s[a]) - ord('0') == 2 else 2\n",
    "            for j in range(ord(s[b]) - ord('0')):\n",
    "                s.append(str(temp))\n",
    "            a = len(s) - 1\n",
    "            b += 1\n",
    "        return s[:n].count('1')\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        s = ['1','2','2']\n",
    "        if n <= 3:\n",
    "            return 1\n",
    "        i = 2\n",
    "        while(len(s) < n):\n",
    "            # 1^3->2  2^3->1\n",
    "            tmp = int(s[-1]) ^ 3\n",
    "            if s[i] == '1':\n",
    "                s.append(str(tmp))\n",
    "            if s[i] == '2':\n",
    "                s.append(str(tmp))\n",
    "                s.append(str(tmp))\n",
    "            i = i + 1\n",
    "        return s[:n].count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        print(s)\n",
    "        s[:3] = \"122\"\n",
    "        print(s)\n",
    "        res = 1\n",
    "        i, j = 2, 3\n",
    "        while j < n:\n",
    "            size = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while size and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    res += 1\n",
    "                j += 1\n",
    "                size -= 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        a = [1]*(n+5)\n",
    "        a[:3] = [1,2,2]\n",
    "        i=2\n",
    "        for j in range(2,n+1):\n",
    "            if a[j]==1:  # 本组数量1，下一个必变\n",
    "                a[i+1] = 3-a[i]\n",
    "                i+=1\n",
    "            else:  # 本组数量2，看看是i分在哪组\n",
    "                # if a[i] == a[i-1]:\n",
    "                a[i+2]=a[i+1] = 3-a[i]\n",
    "                i+=2\n",
    "                         \n",
    "            # print(i,j,a)\n",
    "            if i >= n:\n",
    "                break\n",
    "        print(''.join(map(str,a)))\n",
    "        return a[:n].count(1)\n",
    "                \n",
    "\"\"\"\n",
    "1221121221221121122\n",
    "1221121221221121122\n",
    "1221121221221121122121111\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        if n<4:\n",
    "            return 1\n",
    "        s=['']*n\n",
    "        s[:3]=\"122\"\n",
    "        res=1\n",
    "        i=2\n",
    "        j=3\n",
    "        while(j<n):\n",
    "            size=int(s[i])\n",
    "            num=3-int(s[j-1])\n",
    "            while size and j<n:\n",
    "                s[j]=str(num)\n",
    "                if num==1:\n",
    "                    res+=1\n",
    "                j+=1\n",
    "                size-=1\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magicalString(self, n: int) -> int:\n",
    "        # 双指针: 构造\n",
    "        # strs = [1, 2, 2, 1]\n",
    "        # while len(strs) < n:\n",
    "        #     cnts, strs, cur = strs, [], 1\n",
    "        #     for cnt in cnts:\n",
    "        #         strs += [cur] * cnt\n",
    "        #         cur = 3 - cur\n",
    "        # return strs[:n].count(1)\n",
    "\n",
    "        \n",
    "        if n < 4:\n",
    "            return 1\n",
    "        s = [''] * n\n",
    "        s[:3] = \"122\"\n",
    "        ans, i, j = 1, 2, 3\n",
    "        while j < n:\n",
    "            cnt = int(s[i])\n",
    "            num = 3 - int(s[j - 1])\n",
    "            while cnt and j < n:\n",
    "                s[j] = str(num)\n",
    "                if num == 1:\n",
    "                    ans += 1\n",
    "                j += 1\n",
    "                cnt -= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
